package j_util.sorters;

import java.util.Comparator;
import java.util.List;

public class InsertionSort extends Sort {

    public <T> void sort(List<T> list, int left, int right, Comparator<T> c) {
        resetVariables();
        time = System.currentTimeMillis();
        int i;

        for (i = right; i > left; i--) {
            compareAndExchange(list, i - 1, i, c);
        }
        for (i = left + 2; i <= right; i++) {
            int j = i;
            T value = list.get(i);
            while (j > 0 && less(value, list.get(j - 1), c)) {
                list.set(j, list.get(j - 1));
                j--;
            }
            moves++;
            list.set(j, value);
        }
        time = System.currentTimeMillis() - time;
    }

    public String getName() {
        return "InsertionSort";
    }

    public <T> void sort(List<T> list, Comparator<T> comparator) {
        int left = 0;
        int right = list.size() - 1;
        sort(list, left, right, comparator);
    }
}
